package leetcode;

/***
 * 题目：最大子数组之和
 * 链接：https://leetcode.cn/problems/maximum-subarray/description/
 */
public class MaxSum {
    public static void main(String[] args) {
        int[] arr = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        int max = maxSum(arr);
        System.out.println(max);
    }
    public static int maxSum(int[] arr) {
        // 定义当前最大
        int currMaxSum = arr[0];
        // 当前最大值
        int maxSum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            // currMaxSum和arr[i]相比，currMaxSum大则累加，arr[i]大，则相当于从i位置从头开始
            currMaxSum = Math.max(currMaxSum + arr[i], arr[i]);
            // 这里也是，即使从i开始，只有累加到比上一串更大时间才替换
            maxSum = Math.max(maxSum, currMaxSum);
        }
        return maxSum;
    }
}
